package _18_剑指OfferII;

import java.util.ArrayList;
import java.util.List;

public class _086_剑指OfferII分割回文子字符串 {

    private List<List<String>> result = new ArrayList<>();

    public String[][] partition(String s) {

        dfs(s, 0, new ArrayList<>());


        String[][] arr = new String[this.result.size()][];

        for (int i = 0; i < this.result.size(); i++) {
            arr[i] = new String[this.result.get(i).size()];
            for (int j = 0; j < this.result.get(i).size(); j++) {
                arr[i][j] = this.result.get(i).get(j);
            }
        }
        return arr;
    }

    private void dfs(String s, int index, List<String> list) {
        int len = s.length();
        if (index == len) {
            result.add(new ArrayList<>(list));
            return;
        }

        for (int i = index; i < len; i++) {
            String subStr = s.substring(index, i + 1);
            if (!palindromic(subStr)) continue;

            list.add(subStr);
            dfs(s, i + 1, list);
            list.remove(list.size() - 1);
        }
    }

    private boolean palindromic(String subStr) {
        if (subStr == null || subStr.length() <= 1) {
            return true;
        }

        int start = 0;
        int end = subStr.length() - 1;
        while (start < end) {
            if (subStr.charAt(start) != subStr.charAt(end)) return false;
            start++;
            end--;
        }
        return true;
    }

}
